//    https://www.nowcoder.com/practice/71cde4dee669475f94d8d38832374ada




class Solution
{
public:
    int find(int x, int p[])
    {
        if (p[x] != x) p[x] = find(p[x], p);
        return p[x];
    }

    int citys(vector<vector<int>>& m)
    {
        int n = m.size();
        int p[n];
        for (int i = 0; i < n; i++)
        {
            p[i] = i;
        }

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (m[i][j] == 1 && i != j)
                {
                    int rootI = find(i, p);
                    int rootJ = find(j, p);
                    if (rootI != rootJ)
                    {
                        p[rootI] = rootJ;
                    }
                }
            }
        }

        int count = 0;
        for (int i = 0; i < n; i++)
        {
            if (p[i] == i) count++;
        }

        return count;
    }
};
